package com.leetcode.根据数据结构分类.二叉树;

import com.leetcode.datastructure.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: ZhouBert
 * @date: 2020/11/25
 * @description: https://leetcode-cn.com/problems/check-completeness-of-a-binary-tree/
 */
public class B_958_二叉树的完全性检验 {

	/**
	 * 判断树是否为完全二叉树
	 * 本方法是从流程上去考虑-> 判断每一层的情况！
	 * 所以感觉步骤很多！但是都被我暴力罗列了！
	 * 所以是个笨方法！
	 *
	 * @param root
	 * @return
	 */
	public static boolean isCompleteTree(TreeNode root) {
		//至少一个节点
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		int levelSize = 0;
		int expectValue = 1;
		TreeNode cur = root;
		queue.offer(cur);
		levelSize++;
		boolean happendn = false;
		while (!queue.isEmpty()) {
			if (levelSize != expectValue) {
				//判断是否是叶子节点 - 只能是叶子节点才有可能是完全的 -> 已经进入到最后一层了
				for (int i = 0; i < levelSize; i++) {
					cur = queue.poll();
					if (cur.left != null || cur.right != null) {
						return false;
					}
				}
			} else {
				//本层符合期望值
				for (int i = 0; i < levelSize; i++) {
					cur = queue.poll();
					//对于已经出现 null 的，必须保持后面的都是 null
					//否则，就是保持 not null
					if (cur.left != null) {
						if (happendn) {
							return false;
						} else {
							queue.offer(cur.left);
						}
					} else {
						happendn = true;
					}
					if (cur.right != null) {
						if (happendn) {
							return false;
						} else {
							queue.offer(cur.right);
						}
					} else {
						happendn = true;
					}
				}
				happendn = false;
				expectValue = expectValue * 2;
				levelSize = queue.size();
			}
		}
		return true;
	}


	/**
	 * 这个是从 node 的角度去考虑，情况就不会那么复杂！
	 * 同时还借用了层序遍历的性质来判断靠左的属性！
	 * 真是个好办法！
	 * --
	 * 【需要转换角度好好体会一下！】
	 *
	 * @param root
	 * @return
	 */
	public static boolean isCompleteTree2(TreeNode root) {
		if (root == null) {
			return false;
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		//标记是否应该为叶子节点
		boolean isLeaf = false;
		while (!queue.isEmpty()) {
			TreeNode cur = queue.poll();
			if (isLeaf && !(cur.left == null && cur.right == null)) {
				return false;
			}
			if (cur.left != null && cur.right != null) {
				queue.offer(cur.left);
				queue.offer(cur.right);
			} else if (cur.left == null && cur.right != null) {
				return false;
			} else {
				//后面遍历的必须都是叶子节点
				isLeaf = true;
				// 出现了重复判断！！！！！
				if (cur.left != null) {
					queue.offer(cur.left);
				}
			}
		}
		return true;
	}


	public static boolean isCompleteTree4(TreeNode root) {
		Queue<TreeNode> queue = new LinkedList<>();
		if (root == null) {
			return false;
		}

		TreeNode cur = root;
		//将 根节点 入队
		queue.offer(cur);
		// 当出现一个节点没有子树时，后面肯定不能再有子树了！
		boolean noMoreChild = false;
		while (!queue.isEmpty()) {
			cur = queue.poll();
			if (cur.left != null) {
				if (noMoreChild){
					return false;
				}
				queue.offer(cur.left);
			} else {
				//如果一个节点的左子树为空，但是右子树非空
//				if (cur.right != null) {
//					return false;
//				}
				noMoreChild = true;
			}
			//此时，要么 left != null
			if (cur.right != null) {
				if (noMoreChild){
					return false;
				}
				queue.offer(cur.right);
			}else {
				noMoreChild = true;
			}
		}
		return true;
	}

	/**
	 * 这个是整理 isCompleteTree2 的版本
	 * 基于 在层序遍历的骨架上进行拓展的想法而来。
	 * -- 站在巨人的肩膀上
	 * 这种思路是比较顺的
	 *
	 * @param root
	 * @return
	 */
	public static boolean isCompleteTree3(TreeNode root) {
		if (root == null) {
			return false;
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		boolean isLeaf = false;
		while (!queue.isEmpty()) {
			TreeNode cur = queue.poll();
			if (isLeaf && !(cur.left == null && cur.right == null)) {
				return false;
			}
			if (cur.left != null) {
				queue.offer(cur.left);
			} else if (cur.right != null) {
				//此时 left == null && right != null
				return false;
			}

			if (cur.right != null) {
				//此时 left!=null && right != null
				queue.offer(cur.left);
			} else {
				//此时 left == null && right == null
				//or  left != null && right == null
				isLeaf = true;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		testIsCompleteTree4();

		TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), null));
		boolean completeTree = isCompleteTree(root);
		System.out.println("completeTree = " + completeTree);
		TreeNode root1 = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, null, new TreeNode(6)));
		boolean completeTree2 = isCompleteTree(root1);
		System.out.println("completeTree2 = " + completeTree2);
	}

	/**
	 * 测试 没有任何影响下的我的写法
	 */
	static void testIsCompleteTree4(){
		TreeNode root = TreeNode.stringToTreeNode("[1,2,3,4,5,null,7]");
		boolean completeTree = isCompleteTree4(root);
	}
}
